package LinkList;

/*
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/linked-list/f9izv/
 */

public class _32移除链表元素 {
    public static void main(String[] args) {

    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //dummy结点加双指针  (迭代)
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(-1, head);//dummy是个固定的结点，dummy的next是一开始的head的地址，不管后续head对象如何变化dummy的next都保持不变
        ListNode pre = dummy;//便于使用遍历链表时当前head的前驱
        while (head != null) {
            if (head.val == val) {
                pre.next = head.next;
                head = head.next;
            }else {
                pre = pre.next;
                head = head.next;
            }

        }

        return dummy.next;

    }

    //官解：迭代
//    public ListNode removeElements(ListNode head, int val) {
//        ListNode dummyHead = new ListNode(0);
//        dummyHead.next = head;
//        ListNode temp = dummyHead;
//        while (temp.next != null) {
//            if (temp.next.val == val) {
//                temp.next = temp.next.next;
//            } else {
//                temp = temp.next;
//            }
//        }
//        return dummyHead.next;
//    }

    //官解：递归
    //链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。
    //思路：
    //对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。
    //如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；
    //如果 head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head。
    //上述过程是一个递归的过程。
    //递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
//        public ListNode removeElements(ListNode head, int val) {
//            if (head == null) {
//                return head;
//            }
//            head.next = removeElements(head.next, val);
//            return head.val == val ? head.next : head;
//        }



}
